#include<stdio.h>

struct Node
{
    int next, data;
} node[100001];

int main()
{
    int start_address, num, index;
    scanf("%d%d", &start_address, &num);
    for (int i = 0; i < num; i++)
    {
        scanf("%d", &index);
        scanf("%d%d", &node[index].data, &node[index].next);
    }

    int order[num]; order[0] = start_address;
    for (int i = 1;; i++)
    {
        if (node[order[i - 1]].next == -1) {num = i; break;}
        order[i] = node[order[i - 1]].next;
    }

    int flag = -1, head = 0, tail = num - 1;
    for (int i = 1; i < num; i++, flag *= -1)
    {
        if (flag == -1) {node[order[tail--]].next = order[head];}
        else {node[order[head++]].next = order[tail];}
    }
    node[order[head]].next = -1; index = order[num - 1];

    for (int i = 1; i < num; i++)
    {
        printf("%05d %d %05d\n", index, node[index].data, node[index].next);
        index = node[index].next;
    }
    printf("%05d %d %d\n", index, node[index].data, node[index].next);
    return 0;
}
